package 面试经典150题.链表;

import common.ListNode;

/**
 * @author tmh
 * @date 2024/4/5 15:49
 * @description
 */
public class T21合并两个有序链表 {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        list1.next = node2;
        node2.next = node3;

        ListNode list2 = new ListNode(1);
        ListNode node21 = new ListNode(3);
        ListNode node22 = new ListNode(4);
        list2.next = node21;
        node21.next = node22;

        ListNode listNode = mergeTwoLists(list1, list2);
        while (listNode != null) {
            System.out.print(listNode.val + " ");
            listNode = listNode.next;
        }

    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //定义了一个preHead节点 一个listNode指针（其实都是一样的，只是不同的表述更好理解下）
        ListNode preHead = new ListNode();
        ListNode listNode = preHead;
        while (list1 != null && list2 != null) {
            if (list2.val <= list1.val) {
                listNode.next = list2;
                list2 = list2.next;
            } else {
                listNode.next = list1;
                list1 = list1.next;
            }
            listNode = listNode.next;
        }

        listNode.next = list1 == null ? list2 : list1;

        return preHead.next;
    }
}
